package com.mooc.tree.bak.BinTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author zhang.xin
 * @Description: TODO(这里描述)
 * @Date 2019/12/23
 */
public class BinaryTree implements IBinaryTree{

    BinTreeNode root;

    public BinaryTree(){
        root = null;
    }

    /**
     * 这个方法主要用于测试二叉树的相关操作使用，是一颗固定的二叉树
     */
    public BinTreeNode createBinaryTree(){
        root = new BinTreeNode('A');

        BinTreeNode b = new BinTreeNode('B');
        BinTreeNode c = new BinTreeNode('C');
        root.setLeft(b);
        root.setRight(c);

        BinTreeNode d = new BinTreeNode('D');
        BinTreeNode f = new BinTreeNode('F');
        b.setLeft(d);
        b.setRight(f);

        BinTreeNode g = new BinTreeNode('G');
        BinTreeNode i = new BinTreeNode('I');
        c.setLeft(g);
        c.setRight(i);

        BinTreeNode e = new BinTreeNode('E');
        f.setLeft(e);
        BinTreeNode h = new BinTreeNode('H');
        g.setRight(h);

        return root;
    }

    // 一下是递归的遍历的实现

    /**
     * 递归先序遍历
     * @param root  根结点
     */
    @Override
    public void preOrderTraversal(BinTreeNode root){
        if (root != null) {
            System.out.print(root.getData() + " ");
            preOrderTraversal(root.getLeft());
            preOrderTraversal(root.getRight());
        }
    }

    /**
     * 递归中序遍历
     * @param root 根结点
     */
    @Override
    public void inOrderTraversal(BinTreeNode root) {
        if (root != null) {
            inOrderTraversal(root.getLeft());
            System.out.print(root.getData() +" ");
            inOrderTraversal(root.getRight());
        }
    }

    /**
     * 递归后序遍历
     * @param root 根节点
     */
    @Override
    public void postOrderTraversal(BinTreeNode root) {
        if (root != null) {
            postOrderTraversal(root.getLeft());
            postOrderTraversal(root.getRight());
            System.out.print(root.getData() + " ");
        }
    }

    // 非递归的遍历方式
    @Override
    public void noneRecursiveInOrderTraversal(BinTreeNode root) {
        Stack<BinTreeNode> stack = new Stack<>(); // todo 改成自己定义的栈
        BinTreeNode r = root;
        while (r != null || !stack.empty()) {
            // 把左子树压栈
            while (r != null) {
                stack.push(r);
                r = r.getLeft();
            }
            if (!stack.empty()) {
                BinTreeNode node = stack.pop();
                System.out.print(node.getData() + " ");
                r = node.getRight();
            }
        }
    }

    // 非递归先序遍历
    @Override
    public void noneRecursivePreOrderTraversal(BinTreeNode root) {
        Stack<BinTreeNode> stack = new Stack<>(); // todo 改成自己定义的
        BinTreeNode BT = root;
        while (BT != null || !stack.empty()) {
            while (BT != null) {
                System.out.print(BT.getData() + " ");
                stack.push(BT);
                BT = BT.getLeft();
            }
            if (!stack.empty()) {
                BinTreeNode node = stack.pop();
                BT = node.getRight();
            }
        }
    }

    // 非递归的后序遍历
    @Override
    public void noneRecursivePostOrderTraversal(BinTreeNode root) {
        BinTreeNode r = root;
        Stack<BinTreeNode> stack1 = new Stack<>();
        Stack<BinTreeNode> stack2 = new Stack<>();
        stack2.push(r);
        while (!stack2.empty()) {
            BinTreeNode node = stack2.pop();
            stack1.push(node);
            if (node.getLeft() != null) {
                stack2.push(node.getLeft());
            }
            if (node.getRight() != null) {
                stack2.push(node.getRight());
            }
        }
        while (!stack1.empty()) {
            System.out.print(stack1.pop().getData() + " ");
        }
    }

    // 层序遍历
    @Override
    public void levelOrderTraversal(BinTreeNode root) {
        Queue<BinTreeNode> queue = new LinkedList<>(); // todo 后面换成自己定义的队列
        BinTreeNode r = root;
        queue.add(r);
        while (!queue.isEmpty()) {
            BinTreeNode node = queue.poll();
            System.out.print(node.getData() + " ");
            if (node.getLeft() != null) {
                queue.add(node.getLeft());
            }
            if (node.getRight() != null) {
                queue.add(node.getRight());
            }
        }
    }


    // 测试方法
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinTreeNode root = binaryTree.createBinaryTree();
        // D B F E A G H C I
        // binaryTree.noneRecursiveInOrderTraversal(root);
        // binaryTree.inOrderTraversal(root);
        // A B D F E C G H I
        // binaryTree.noneRecursivePreOrderTraversal(root);
        // binaryTree.preOrderTraversal(root);
        // D E F B H G I C A
        // binaryTree.postOrderTraversal(root);
        // binaryTree.noneRecursivePostOrderTraversal(root);
        // A B C D F G I E H
        binaryTree.levelOrderTraversal(root);
    }
}
